package leetcode_121_140;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class candy_135 {
    /**
     * 需要按照以下要求，给这些孩子分发糖果：
     * 每个孩子至少分配到 1 个糖果。
     * 相邻两个孩子评分更高的孩子会获得更多的糖果。
     * @param ratings
     * @return 需要准备的 最少糖果数目 。
     */
    public int candy(int[] ratings) {
        /**
         * 需要考虑的主要有两点
         * 1，是顺序遍历时，出现无法确定极高点需要给定的最小糖果
         * 因为可能出现给极大值点孩子的糖果可能小于后边连续下降的学生数量
         * 思路是，记录每一个极低点和极高点位置
         * 为了最少糖果数目，每一个极低点都设置为1，并且连续等差为1的上升，
         * 每一个极高点设置为左右升序和降序的个数较大的那个
         * 2，是相等评分时，一边可以更低,这种情况较复杂，想法是只计算所有不包含相邻相等元素的数组，其余的剩余的均赋值1
         * 思路失败
         */
        int ans=0;
        for(int i=0;i<ratings.length-1;i++){
            if (ratings[i] == ratings[i - 1] && ratings[i] == ratings[i + 1]) {  //与前后评分都相等，直接给一个糖果
                ans += 1;
                continue;
            }
            while(ratings[i] != ratings[i - 1]){

            }
        }
        return ans;
    }

    /**
     * 高解思路
     * 将条件规则，分为两部分
     * 1，左边评分比右边同学低时，右边糖果大于左边
     * 2，右边评分比左边同学低时，左边糖果大于右边
     * 进行两个方向遍历，从左到右遍历处理1，从右到左处理2
     */
    public int candy2(int[] ratings) {
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        //所有人首先都给1个糖果
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        //从左到右遍历处理1
        for(int i = 1; i < ratings.length; i++)
            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        int count = left[ratings.length - 1];

        //从右到左处理2
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            count += Math.max(left[i], right[i]);
        }
        return count;
    }

}
